#include <stdio.h>
#include <stdlib.h>

typedef struct {
    char NES; // 生成式的左部，非终结符
    char str[20]; // 生成式的右式
    int len; // 生成式右部的长度
} Gen;
typedef struct {
    char ch; // 记录非终结符
    int mark; // 标志其是否为导空符
} Terminal;
#define NEND_MAX 10 // 非终结符最大数量
#define STR_MAX 100
// 判断一条产生式是否可以导空
/**
 * NEnd:非终止符集
 * sLen:非终止符数量
 * gen:一条生成式
*/
int computerEpsilon(Gen *gen, Terminal *NEnd, int sLen){
    int flag = 1;   // 默认为导空符
    int i,j;
    for(i=0; i < (gen->len); i++){
        // 如果|前的一条产生式不导空，则将flag置为1再次尝试
        if(gen->str[i] == '|' && flag == 0){
            flag = 1;
        }
        else{
            for(j=0; j < sLen; j++){
                if(gen->str[i] == NEnd[j].ch){
                    // 终止符不是导空符
                    if(NEnd[j].mark == 0)  flag = 0;
                    break;
                }
            }
            if(j == sLen && gen->str[i] != '$'){
                flag = 0;
            }
        }
    }
    if(flag == 1){
        for(j=0; j<sLen && NEnd[j].ch != gen->NES; j++);
        // 未变化则返回0
        if(NEnd[j].mark == 1)   return 0;
        NEnd[j].mark = 1;
        return 1;
    }
    return 0;
}
// 遍历生成式集合，得到不可终止非终结符
Terminal* getEndSet(int* length)
{
    FILE* fp = NULL;
    fp = fopen("codes/practice5.txt", "r");
    if(fp==NULL){
        printf("文件不存在！");
        exit(1);
    }
    // 获取终止符集合
    
    int i = 0;
    char str[STR_MAX];
    // NEnd：非终结符集合
    Terminal* NEnd = (Terminal*)malloc(sizeof(Terminal) * NEND_MAX);
    fgets(str, STR_MAX, fp);
    int count = 0;
    for (i = 0; str[i] != '#'; i += 2) {
        NEnd[count].ch = str[i];
        NEnd[count++].mark = 0; // 初始时都为非导空符
    }
    *length = count;


    // 生成式集合格式化，包括长度，生成式右部，和生成式左部
    int len = 0; // len记录生成式的条数
    Gen* genSet[10];
    while (fp != NULL) {
        int index = 0;
        fgets(str, STR_MAX, fp);
        if (str[0] == '#')
            break; // 检测到文件终止符时结束循环
        Gen* newGen = (Gen*)malloc(sizeof(Gen));
        newGen->NES = str[0];
        while (str[index] != '>')
            index++;
        index++;
        count = 0;
        while (str[index] != '\n')
            newGen->str[count++] = str[index++];
        newGen->len = count;
        genSet[len] = newGen;
        len += 1;
    }
    fclose(fp);


    // 计算出导空符集

    // flag标志NEnd集合发生改变
    int flag = 1, change;   
    while(flag == 1){
        flag = 0;
        for(i=0; i<len; i++){
            change = computerEpsilon(genSet[i],NEnd,*length);
            if(change == 1) flag = 1;
        }
    }
    return NEnd;
}

int main()
{
    int len;
    Terminal* Set = getEndSet(&len);
    int i;
    printf("导空符如下：");
    for (i = 0; i < len; i++) {
        if(Set[i].mark == 1)
            printf("%c ", Set[i].ch);
    }
    return 0;
}